//前缀和 区间次方和
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll N = 1e6+9;
const ll mod = 1e9+7;
ll a[6][N];
ll prefix[6][N];

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	ll m=0,n=0;
	cin>>n>>m;
	for(ll i = 1; i <= n; i++)
		cin>>a[1][i];
	//创建出1到5次方的5个数组
	for(ll i = 2; i <= 5; i++)
	{
		for(ll j = 1; j <= n; j++)
		{
			a[i][j] = a[i-1][j] * a[1][j]%mod;
		}
	}
	//创建出1到5次方5个数组的前缀和数组
	for(ll i = 1; i <= 5; i++)
	{
		for(ll j = 1; j<= n; j++)
		{
			prefix[i][j] = (prefix[i][j-1] + a[i][j])%mod;
		}
	}
	
	//由前缀和计算出给定区间的次方和
	for(ll i = 1; i <= m; i++)
	{
		ll l=0,r=0,k=0;
		cin>>l;
		cin>>r;
		cin>>k;
		cout << (mod + prefix[k][r] - prefix[k][l-1])%mod <<endl;
		
	}
	return 0;
}
